Kotlin Computational Geometry/io.github.cponfick.kompgeom.algorithms.intersection

Package-level declarations

Types

class BentleyOttmann(segments: Collection<Segment2<*>>, precision: DoubleEquivalence = DEFAULT_DOUBLE_EQUIVALENCE) : Algorithm<List<SegmentIntersection>>

Reports intersections between two-dimensional segments. The sweep uses a shear to make vertical segments x-monotone; reported coordinates remain in the original coordinate system. The status is an order-maintenance tree: its keys never depend on the current sweep coordinate.

SegmentIntersection

data class SegmentIntersection(val first: Int, val second: Int, val intersection: IntersectionData<Vec2>)

A pair of input segments and their intersection returned by BentleyOttmann.

ShamosHoey

class ShamosHoey(segments: Collection<Segment2<*>>, precision: DoubleEquivalence = DEFAULT_DOUBLE_EQUIVALENCE) : Algorithm<Boolean>

Detects whether any pair of two-dimensional segments intersects. Only endpoint events are needed: each newly neighboring pair is tested immediately, as in the Shamos–Hoey algorithm (Algorithm 1). This takes O(n log n) time and O(n) space with the AVL order-maintenance tree under consistent geometric predicates. Near the floating-point tolerance boundary, the sweep can disagree with pairwise intersection tests (see precision tracking issue). Shared endpoints and overlaps count as intersections. Polygon simplicity, which allows only shared corners of consecutive edges, is handled separately by polygonHasSelfIntersection.